#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <string.h>
#define EPS 1E-8
#define TRUE 1
#define FALSE 0
#define NEWLINE putchar('\n')
#define READ(x)   scanf("%d",&x)
#define WRITELN(x)  printf("%d\n",x)
#define ABS(x) (((x)>0)?(x):(-(x))) //¾ø¶ÔÖµ
#define MAX(x,y) ((x)>(y)?(x):(y)) //×î´óÖµ
#define MIN(x,y) ((x)<(y)?(x):(y)) //×îÐ¡Öµ
#define SQUARE(x) ((x)*(x))   //Æ½·½
#define IMPLY(x,y)  (!(x)||(y))    /*Âß¼­ÔÌº¬x->yµÄ¶¨Òå*/
#define FEQUAL(x,y) ABS((x)-(y))<=EPS //¸¡µãÏàµÈ
#define SIGN(x) (((x)>0)?1:((x)<0)?-1:0) //·µ»ØÒ»¸ö±í´ïÊ½µÄ·ûºÅ
typedef long long LL;
typedef long double LD;
typedef unsigned int UINT;
typedef unsigned long long ULL;
typedef char BYTE;
typedef char BOOL;
/**
 * ÓÃÓÚqsortµÄÏ´ÅÆËã×Ó
 */
int compRand(const void *a, const void *b) {
  return rand() % 3-1;
}

/**
 * ×÷ÓÃÊÇ½«Êý×éÇ°n¸öÔªËØÏ´ÂÒ²úÉúËæ»úË³Ðò
 */
void shuffle(int *a, int n) {
  qsort(a, n, sizeof(int), compRand);
}

/**
 * Êý×é´òÓ¡³ÌÐò,´òÓ¡Êä³öÊý×éµÄÇ°n¸öÔªËØ
 */
void printArr(int *a, int n) {
  int i;
  for (i = 0; i < n; i++)
    printf("%d ", a[i]);
  NEWLINE;
}

/**
 * ±äÁ¿½»»»£¬CÖÐ±ØÐëÊ¹ÓÃÖ¸Õë²ÅÄÜ´ïµ½¼ä½ÓÐÞ¸Ä±äÁ¿µÄÐ§¹û
 */
void swap(int *a, int *b) {
  int t =  *a;
  *a =  *b;
  *b = t;
}

/**
 * ÀûÓÃrand()º¯Êý²úÉú[start,end]Ö®¼äµÄËæ»úÊý
 */
int doss(int start, int end) {
  if (start > end)
    swap(&start, &end);
  return rand() % (end - start + 1) + start;
}

/**
 * ²»¶Ï²úÉú[start,end]Ö®¼äµÄËæ»úÊý£¬Ö±µ½²úÉúµ½targetÎªÖÁ
 */
void P01(int start, int end, int target) {
  srand(time(NULL));
  int temp, len = 0;
  if (start > end)
    swap(&start, &end);
  if (target < start || target > end)
    printf("%d is not in in the range of [%d,%d]\n!", target, start, end);
  else {
    do {
      temp = doss(start, end);
      printf("%d->", temp);
      len++;
    } while (temp != target);
    printf("\nAfter %d times to get %d\n", len, temp)
      ;
  }
}

/**
 * ×î´ó¹«Ô¼Êý
 */
int gcd(int a, int b) {
  return b ? gcd(b, a % b): a;
}

/**
 * ×îÐ¡¹«±¶Êý
 */
int lcm(int a, int b) {
  return a / gcd(a, b) *b;
}

/**
 * ¼ÆËã[start,end]Ö®¼ä±»rÕû³ýµÄËùÓÐÊýÖ®ºÍ£¬³£ÊýËã·¨£¨µÈ²îÊýÁÐµÄ·½·¨£©
 */
int sum(int start, int end, int r) {
  if (start > end)
    swap(&start, &end);
  start = (start + r - 1) / r * r;
  end = end / r * r;
  int n = (end - start) / r + 1;
  return (start + end) *n >> 1;
}

void P02(int start, int end, int p, int q) {
  if (start > end)
    swap(&start, &end);
  printf("%d\n", sum(start, end, lcm(p, q)));
}

/**
 * ´òÓ¡Êý×ÖÁâÐÎ
 */
void P03(int size) {
  int i, j, n = 2 * size - 1;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++)
      if (ABS(i - size) + ABS(j - size) >= size)
    //º¯Êý·½·¨
        putchar(' ');
      else
        putchar('A' - 1+size - ABS(i - size) - ABS(j - size));
    NEWLINE;
  }
}

/**
 * ²»¶¨·½³Ìx+y+z==total &&pa*x+pb*y+pc*z==moneyµÄÓÅ»¯Ã¶¾ÙÍ¨ÓÃ·½·¨
 */
void uniSolve(double pa, double pb, double pc, int total, int money) {
  int a, b, c;
  for (a = 0; a <= MIN(total, money / pa); a++)
  for (b = 0; b <= MIN(total - a, money / pb); b++) {
    c = total - a - b;
    if (FEQUAL(a *pa + b * pb + c * pc, money))
      printf("%d\t%d\t%d\n", a, b, c);
  }
}

void P04() {
  uniSolve(3, 2, 1 / 2., 100, 100);
}

void P05() {
  uniSolve(2, 4, 2. / 9, 100, 100);
}

/**
 * ÕÔÇ®ËïÀîÖÜµÄÄ£Äâ·¨£¬ÓÃ01234Ä£ÄâÔ²×ÀµÄ×ø·¨
 */
int isLeft(int a, int b) {
  //ÕâÊÇ»ù´¡Ä£ÐÍ
  return b == a + 1 || (a == 4 && b == 0);
}

int isRight(int a, int b) {
  //µ÷ÓÃisLeft¼ò»¯¶¨Òå
  return isLeft(b, a);
}

int isNeighbour(int a, int b) {
  //Í¬ÉÏ
  return isLeft(a, b) || isRight(a, b);
}

void P06() {
  int s[] =  {
    1, 2, 3, 4
  };
  int zhao = 0, qian, sun, li, zhou; //ÒòÎªÊÇ»·ÐÎ£¬ËùÒÔ¿ÉÒÔ¹Ì¶¨ÕÔµÄ×ùÎ»
  int zp, zq, lp, lq;
  do {
    shuffle(s, 4); //ºÍÏÂÒ»ÐÐÒ»Æð²úÉú1,2,3,4µÄËæ»úÅÅÁÐ¸³¸øÇ®ËïÀîÖÜ
    qian = s[0], sun = s[1], li = s[2], zhou = s[3];
    zp = isNeighbour(zhao, qian);
    zq = (isLeft(sun, qian) || isLeft(li, qian));
    lp = isLeft(qian, sun);
    lq = isNeighbour(li, sun);
  } while (zp || zq || lp || lq); //·´¸´ÕÒÖ±µ½ÕÒµ½Ò»×é´ð°¸
  printf("%d ", zhao);
  printArr(s, 4);
}

/**
 * ÖÊÊý¼ì²âµÄ¼òµ¥ÓÅ»¯Ëã·¨
 */
int isPrime(int n) {
  n = ABS(n);
  if (n < 2)
    return 0;
  if (n == 2)
    return 1;
  if (n % 2 == 0)
    return 0;
  int t = sqrt(n), i;
  for (i = 3; i <= t; i += 2)
    if (n % i == 0)
      return 0;
  return 1;
}

void P07() {
  int start = 100, end = 999, h, t, d, i, cnt = 0;
  for (i = start; i <= end; i++) {
    h = i / 100, t = (i / 10) % 10, d = i % 10;
    if (h != t && t != d && d != h && t > h + d && !isPrime(t + h)) {
      printf("%d ", i);
      if (++cnt % 5 == 0)
        NEWLINE;
    }
  }
  NEWLINE;
}

//Ö¸ÅÉÎÊÌâµÄÇî¾Ù·¨
void P08() {
  int a, b, c, d, e;
  for (a = 0; a <= 1; a++)
    for (b = 0; b <= 1; b++)
      for (c = 0; c <= 1; c++)
        for (d = 0; d <= 1; d++)
  for (e = 0; e <= 1; e++) {
    if (a + b + c + d + e == 3 && a + c != 2 && b + c != 0 && IMPLY(c, d + e == 1) && b + c + d != 3 && IMPLY(b, d + e != 2)) {
      if (a)
        putchar('A');
      if (b)
        putchar('B');
      if (c)
        putchar('C');
      if (d)
        putchar('D');
      if (e)
        putchar('E');
      NEWLINE;
    }
  }
  NEWLINE;
}

void P09() {
  char line[80], buffer[80],  *p = line;
  int i = 0;
  gets(line);
  while (*p) {
    i = 0;
    while (isdigit(*p)) {
      buffer[i++] =  *p++;
    }
    buffer[i++] = '\0';
    if (strlen(buffer))
      puts(buffer);
    buffer[0] = 0;
    p++;
  }
}

void P10() {
  int s[] =  {
    1, 2, 3
  };
  int a, b, c, ap, aq, bp, bq, cp, cq;
  do {
    shuffle(s, 3);
    a = s[0], b = s[1], c = s[2];
    ap = (b == 2 && c == 2), aq = (a == 1);
    bp = (b <= 2), bq = (c == 3);
    cp = (a != 2), cq = (b != 1);
  } while (!(a + ap + aq == 3 && b + bp + bq == 3 && c + cp + cq == 3));
  printArr(s, 3)
    ;
}

//·ÖÌÇ¹û
void P11() {
  int a, A, b, B, c, C, d, D, n = 64;
  for (A = n / 2; A <= n; A++)
    for (B = 0; B <= n - A; B++)
  for (C = 0; C <= n - B - C; C++) {
    D = n - A - B - C;
    a = A, b = B, c = C, d = D;
    a -= b + c + d, b += b, c += c, d += d;
    b -= a + c + d, a += a, c += c, d += d;
    c -= a + b + d, a += a, b += b, d += d;
    d -= a + b + c, a += a, b += b, c += c;
    if (a == b && b == c && c == d )
        printf("%d %d %d %d\n", A, B, C, D);
  }
}

void P12() {
  LL x, len, wid, head, mid, tail, step;
  scanf("%lld", &x);
  len = log10(x) + 1;
  wid = (len + 2) / 3;
  step = powf(10, wid);
  tail = x % step;
  x /= step;
  mid = x % step;
  x /= step;
  head = x;
  printf("%lld\t%lld\t%lld\n", head, mid, tail);
  printf("%lld", head + tail - mid);
}

void P13() {
  char line[80], buffer[80],  *p = line;
  int i = 0;
  gets(line);
  while (*p) {
    i = 0;
    while (isalpha(*p)) {
      buffer[i++] =  *p++;
    }
    buffer[i++] = '\0';
    if (strlen(buffer))
      puts(buffer);
    buffer[0] = 0;
    p++;
  }
}

//Ö¸ÅÉÎÊÌâ14
void P14() {
  int a, b, c, d;
  int ta, tb, tc, td;
  for (a = 0; a <= 1; a++)
    for (b = 0; b <= 1; b++)
      for (c = 0; c <= 1; c++)
  for (d = 0; d <= 1; d++) {
    ta = d, tb = c, tc = !c, td = !tc;
    if (ta + tb + tc + td == 2 && a + b + c + d == 1)
          printf("%d %d %d %d\n", a, b, c, d);
  }
}

//²¶ÓãµÝÍÆ·½·¨
void P15(int n) {
  int a[100], i;
  a[n - 1] = 1;
  for (i = n - 2; i >= 0; i--)
    a[i] = n * a[i + 1] + 1;
  for (i = 0; i < n; i++)
    printf("%d ", a[i]);
  NEWLINE;
}

//¸¨Öúº¯Êý£º¼ÆËãÕûÊýnµÄ¸÷Î»Êý×ÖÖ®ºÍ£¬Ò²¿ÉÒÔ×ª»¯Îª×Ö·û´®À´Çó
int digitSum(int n) {
  int s;
  for (s = 0; n > 0;) {
    s += n % 10;
    n /= 10;
  }
  return s;
}

void P16(int len) {
  int i, cnt = 4;
  for (i = powf(10, len - 1); i < powf(10, len); i++) {
    if (i % digitSum(i) == 0) {
      printf("%d ", i);
      if (++cnt % 5 == 0)
        NEWLINE;
    }
  }
}
void P17() {
  char s[100];
  int n, m;
  for (n = 6;; n += 10) {
    sprintf(s, "%d%d", n % 10, n / 10);
    sscanf(s, "%d", &m);
    if (m == 4 *n) {
      printf("%d*4=%d\n", n, m);
      break;
    }
  }
}

/**
 * Í³¼ÆÕûÊýnµÄÊ®½øÖÆ±íÊ¾ÖÐdigitµÄ¸öÊýdigitÊÇÒ»Î»Êý
 */
int count(int n, int digit) {
  int s;
  for (s = 0; n > 0;) {
    if (n % 10 == digit)
      s++;
    n /= 10;
  }
  return s;
}

//Ð¡Ã÷¿´ÊéÎÊÌâ
void P18(int n) {
  int i, sum = 0;
  for (i = 1; sum < n; i++)
    sum += count(i, 1);
  if (sum == n)
    WRITELN(i);
  else
  //Õâ¸öÈÝÒ×ºöÊÓ
    puts("IMPOSSIBLE!");
}

void P19() {
  int a, b;
  READ(a);
  READ(b);
  printf("%6d\n+%5d\n--------\n%6d\n", a, b, a + b);
}

void P20() {
  uniSolve(3, 2, 1, 30, 50);
}
